# LeetCode 160、相交链表

# 一、题目描述

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

img

在节点 c1 开始相交。

注意:

  • 如果两个链表没有交点,返回 null。
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

# 二、题目解析

# 1、模拟

首先假设 A 、B 两个链表是有相交节点的情况。

img

相交链表.002

img

相交链表.003

img

相交链表.004

img

相交链表.005

img

相交链表.006

img

相交链表.007

img

相交链表.008

img

相交链表.009

img

相交链表.010

img

相交链表.011

再假设 A 、B 两个链表是没有相交节点的情况。

img

相交链表.012

img

相交链表.013

img

相交链表.014

img

相交链表.015

# 2、规律

也就是说,无论 A、B 两个链表是否有相交点,最终都会指向一个相同的节点,要么是它们的公共尾部,要么是 NULL。

让指针 pointApointB 分别指向链表 A 和链表 B 的头结点,之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。

  • 当指针 pointA 遍历到链表 A 的尾节点时,此时指针 pointA 走了 a 个节点,将指针 pointA 指向链表 B 的头部,继续向后遍历,直至走到 c1,此时指针 pointA 总共走了 a + ( b - c ) 步。
  • 当指针 pointB 遍历到链表 B 的尾节点时,此时指针 pointB 走了 b 个节点,将指针 pointB 指向链表 A 的头部,继续向后遍历,直至走到 c1,此时指针 pointB 总共走了 b + ( a - c ) 步。

根据数学知识,a + ( b - c ) = b + ( a - c ) ,如果 c > 0,表明两链表有公共尾部, c1 存在,两两链表同时到达 c1;如果 c = 0,表明两链表没有公共尾部,指针 pointApointB 都指向 NULL

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界判断
        if (headA == null || headB == null) return null;
        
        // 设置一个指针 pointA,指向链表 A 的头节点
        ListNode pointA = headA;
        
        // 设置一个指针 pointB,指向链表 B 的头节点
        ListNode pointB = headB;

        // 指针 pointA 和 指针 pointB 不断向后遍历,直到找到相交点
        // 不用担心会跳不出这个循环,实际上在链表 headA 长度和链表 headB 长度的之和减一
        // pointA 和 pointB 都会同时指向 null
        // 比如 headA 的长度是 7,headB 的长度是 11,这两个链表不相交
        // 那么 pointA 移动了 7 + 11 - 1 次之后,会指向 null
        // pointB 移动了 7 + 11 - 1  次之后,也指向 null
        // 这个时候就跳出了循环
        while (pointA != pointB) {
            // 指针 pointA 一开始在链表 A 上遍历,当走到链表 A 的尾部即 null 时,跳转到链表 B 上 
            if( pointA == null){
                // 指针 pointA 跳转到链表 B 上  
                pointA = headB;
            }else{
                // 否则的话 pointA 不断的向后移动
                pointA = pointA.next;
            }

             // 指针 pointB 一开始在链表 B 上遍历,当走到链表 B 的尾部即 null 时,跳转到链表 A 上 
            if( pointB == null){
                // 指针 pointA 跳转到链表 B 上  
                pointB = headA;
            }else{
                // 否则的话 pointB 不断的向后移动
                pointB = pointB.next;
            }
        }
        
        // 1、此时,pointA 和 pointB 指向那个相交的节点,返回任意一个均可
        // 2、此时,headA 和 headB 不相交,那么 pointA 和 pointB 均为 null,也返回任意一个均可
        return pointA;
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 边界判断
        if (headA == NULL || headB == NULL) return NULL;
        
        // 设置一个指针 pointA,指向链表 A 的头节点
        ListNode *pointA = headA;
        
        // 设置一个指针 pointB,指向链表 B 的头节点
        ListNode *pointB = headB;

        // 指针 pointA 和 指针 pointB 不断向后遍历,直到找到相交点
        // 不用担心会跳不出这个循环,实际上在链表 headA 长度和链表 headB 长度的之和减一
        // pointA 和 pointB 都会同时指向 null
        // 比如 headA 的长度是 7,headB 的长度是 11,这两个链表不相交
        // 那么 pointA 移动了 7 + 11 - 1 次之后,会指向 null
        // pointB 移动了 7 + 11 - 1  次之后,也指向 null
        // 这个时候就跳出了循环
        while (pointA != pointB) {
            // 指针 pointA 一开始在链表 A 上遍历,当走到链表 A 的尾部即 null 时,跳转到链表 B 上 
            if( pointA == NULL){
                // 指针 pointA 跳转到链表 B 上  
                pointA = headB;
            }else{
                // 否则的话 pointA 不断的向后移动
                pointA = pointA->next;
            }

             // 指针 pointB 一开始在链表 B 上遍历,当走到链表 B 的尾部即 null 时,跳转到链表 A 上 
            if( pointB == NULL){
                // 指针 pointA 跳转到链表 B 上  
                pointB = headA;
            }else{
                // 否则的话 pointB 不断的向后移动
                pointB = pointB->next;
            }
        }
        
        // 1、此时,pointA 和 pointB 指向那个相交的节点,返回任意一个均可
        // 2、此时,headA 和 headB 不相交,那么 pointA 和 pointB 均为 null,也返回任意一个均可
        return pointA;
    }
};

# 3、Python 代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

        # 边界判断
        if( headA == None or headB == None ): 
            return None

        # 设置一个指针 pointA,指向链表 A 的头节点
        pointA = headA

        # 设置一个指针 pointB,指向链表 B 的头节点
        pointB = headB

        # 指针 pointA 和 指针 pointB 不断向后遍历,直到找到相交点
        # 不用担心会跳不出这个循环,实际上在链表 headA 长度和链表 headB 长度的之和减一
        # pointA 和 pointB 都会同时指向 null
        # 比如 headA 的长度是 7,headB 的长度是 11,这两个链表不相交
        # 那么 pointA 移动了 7 + 11 - 1 次之后,会指向 null
        # pointB 移动了 7 + 11 - 1  次之后,也指向 null
        # 这个时候就跳出了循环
        while pointA != pointB:
            # 指针 pointA 一开始在链表 A 上遍历,当走到链表 A 的尾部即 null 时,跳转到链表 B 上 
            if pointA == None:
                # 指针 pointA 跳转到链表 B 上  
                pointA = headB
            else:
                # 否则的话 pointA 不断的向后移动
                pointA = pointA.next
            # 指针 pointB 一开始在链表 B 上遍历,当走到链表 B 的尾部即 null 时,跳转到链表 A 上 
            if pointB == None:
                # 指针 pointA 跳转到链表 B 上  
                pointB = headA
            else:
                # 否则的话 pointB 不断的向后移动
                pointB = pointB.next
        
        # 1、此时,pointA 和 pointB 指向那个相交的节点,返回任意一个均可
        # 2、此时,headA 和 headB 不相交,那么 pointA 和 pointB 均为 null,也返回任意一个均可
        return pointA

# 四、复杂度分析

时间复杂度:O(m+n),其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。

空间复杂度:O(1)。